#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>

#if 0
/******************** 01背包 ****************/
// N个物品，背包容量为V，每个物品只能用一次。求能装得下的最大价值
// https://www.acwing.com/problem/content/2/

const int N = 1010; // 物品和体积 <= 1000
int dp[N][N], w[N], v[N]; 
// dp[i][j]表示 只考虑前i件物品，能凑出来的体积不超过j的最大价值
// dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); // 1、不选第i件物品，2、选 
void test01dp()
{
    int n, V;
    scanf("%d %d", &n, &V);
    for(int i = 1; i <= n; ++i) scanf("%d %d", &v[i], &w[i]);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= V; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    printf("%d", dp[n][V]);
    /*优化成一维：
    for(int i = 1; i <= n; ++i)
        for(int j = V; j >= v[i]; --j)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    printf("%d", dp[V]);
    */
}

/******************** 完全背包 *******************/
// N个物品，背包容量为V，每个物品能用无限次。求能装得下的最大价值

const int N = 1010;
int dp[N][N], w[N], v[N];
// dp[i][j]表示 只考虑前i件物品，能凑出来的体积不超过j的最大价值。下面为了方便，用v表示v[i]
// dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w, dp[i-1][j-2v]+2w, dp[i-1][j-3v]+3w ...)，直到拿的第i件物品总体积超过 j 为止
// 而dp[i][j-v] = max(        dp[i-1][j-v],   dp[i-1][j-2v]+w,  dp[i-1][j-3v]+2w ...)
// dp[i][j] = max(dp[i-1][j], dp[i][j-v] + w);
void testCompleteDp()
{
    int n, V;
    scanf("%d %d", &n, &V);
    for(int i = 1; i <= n; ++i) scanf("%d %d", &v[i], &w[i]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= V; ++j)
        {
            // for(int k = 0; k * v[i] <= j; ++k)
            //     dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
            // //优化：
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    printf("%d", dp[n][V]);

    /*优化成一维:
    for(int i = 1; i <= n; ++i)
        for(int j = v[i]; j <= V; ++j)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    printf("%d", dp[V]);
    */
}

/******************** 多重背包I *******************/
// N个物品，背包容量为V，每个物品有s[i]个。求能装得下的最大价值
const int N = 110;
int dp[N][N], v[N], w[N], s[N];
// dp[i][j]表示 只考虑前i件物品，能凑出来的体积不超过j的最大价值
// dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w, dp[i-1][j-2v]+2w, ... dp[i-1][j-sv] + sw); 前提是j >= sw
void testMultipleDp1()
{
    int n, V;
    cin >> n >> V;
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= V; ++j)
            for(int k = 0; k <= s[i] && k*v[i] <= j; ++k)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
    cout << dp[n][V];
    /*优化成一维
    for(int i = 1; i <= n; ++i)
        for(int j = V; j >= v[i]; ++j)
            for(int k = 1; k <= s[i] && k*v[i] <= j; ++k)
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
    cout << dp[V];
    */
}

// 多重背包问题的二进制优化，二进制优化
const int N = 12000, V = 2010; // 物品种类N <= 1000, 物品个数s[i] <= 2000, 最多拆成11个数
int dp[N][V], v[N], w[N];
void testMultipleDp2()
{
    // n:物品种类， m:背包容量，cnt分解后的物品个数
    int n, m, cnt = 0;
    cin >> n >> m; 
    for(int i = 1; i <= n; ++i)
    {
        int a, b, s; // 体积，价值，个数
        scanf("%d %d %d", &a, &b, &s); 
        int k = 1, sum = 0;
        for(; sum + k <= s; sum += k, k <<= 1)
        {
            ++cnt;
            v[cnt] = k * a;
            w[cnt] = k * b;
        }
        if(s - sum > 0)
        {
            ++cnt;
            v[cnt] = (s - sum) * a;
            w[cnt] = (s - sum) * b;
        }
    }

    // 转换为 01背包
    for(int i = 1; i <= cnt; ++i)
        for(int j = 1; j <= m; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout << dp[cnt][m];

    /*内存可能会溢出，优化成一维
    for(int i = 1; i <= cnt; ++i)
        for(int j = m; j >= v[i]; --j)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[m];
    */ 
}

/******************** 分组背包 *******************/
// N组物品，背包容量为V。
const int N = 110;
int w[N][N], v[N][N], s[N];
int dp[N][N];
// dp[i][j] 只考虑前 i 组，容量不超过 j 的最大价值
// 第i组不选，第i组选第一个物品，选第二个物品，...
// dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k])
void testGroupDp()
{
    int n, V;
    scanf("%d %d", &n, &V);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &s[i]);
        for(int j = 1; j <= s[i]; ++j)  
            scanf("%d %d", &v[i][j], &w[i][j]);
    }

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= V; ++j)
        {
            // k = 0时，表示不选第i组物品.由于v[i][0]、w[i][0]都为0, dp[i - 1][j - v[i][k]] + w[i][k]就是dp[i - 1][j]
            for(int k = 0; k <= s[i]; ++k)
                if(j >= v[i][k])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
        }
    }
    printf("%d", dp[n][V]);

    /* 优化成一维
    for(int i = 1; i <= n; ++i)
    {
        for(int j = V; j >= 1; --j)
        {
            for(int k = 0; k <= s[i]; ++k)
                if(j >= v[i][k])
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
        }
    }
    printf("%d", dp[V]);
    */
}


/******************** 区间dp *******************/
// // https://www.acwing.com/problem/content/284/
// const int N = 310, INF = 1e9;
// int f[N][N];
// int a[N], sum[N];
// int main()
// {
//     int n;
//     scanf("%d", &n);
//     for(int i = 1; i <= n; ++i) 
//     {
//         scanf("%d", a + i);
//         sum[i] = sum[i - 1] + a[i];
//     }
//     for(int i = 0; i <= n; ++i)
//     {
//         for(int j = 0; j <= n; ++j)
//             if(i == j) f[i][j] = 0;
//             else f[i][j] = INF;
//     }
//     for(int i = 1; i <= n; ++i)
//     {
//         for(int j = i - 1; j >= 1; --j)
//         {
//             for(int k = j; k <= i; ++k)
//             {
//                 f[i][j] = min(f[i][j], f[j][k] + f[k + 1][i] + sum[i] - sum[j - 1]);
//             }
//             printf("%d %d %d\n", j, i, f[i][j]);
//         }
//     }
//     printf("%d", f[n][1]);
//     return 0;
// }

/******************** 编辑距离 ********************/
// // https://www.acwing.com/problem/content/901/
// const int N = 1010;
// char s[N][12];
// char t[12];
// int n, m, k;
// int min_edi()
// {
//     int dp[12][12], cnt = 0, n2 = strlen(t + 1);
//     for(int i = 0; i < n; ++i)
//     {
//         int n1 = strlen(s[i] + 1); // s[i] 的长度
//         memset(dp, 0, sizeof dp);
//         for(int j = 0; j <= n2; ++j)
//             dp[0][j] = j;
        
//         for(int j = 1; j <= n1; ++j)
//         {
//             dp[j][0] = j; // 必须要加
//             for(int k = 1; k <= n2; ++k)
//             {
//                 if(s[i][j] == t[k]) 
//                     dp[j][k] = dp[j - 1][k - 1];
//                 else
//                     dp[j][k] = min(dp[j - 1][k], min(dp[j - 1][k - 1], dp[j][k - 1])) + 1;
//             }
//         }
//         if(dp[n1][n2] <= k)  ++cnt;
//     }
//     return cnt;
// }
// int main(){
//     scanf("%d %d", &n, &m);
//     for(int i = 0; i < n; ++i)  scanf("%s", s[i] + 1);
//     while(m--)
//     {
//         scanf("%s %d", t + 1, &k);
//         printf("%d\n", min_edi());
//     }
//     return 0;
// }

/*************** 数位dp ******************/
#include<iostream>
using namespace std;

// 求1~n中，x出现的个数
const int ten[9] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000 };
int count(int n, int x)
{
    int sum = 0;
    if(n == 0) return 0;
    
    //计算求1~n中，x在每一位出现的个数
    for(int j = n, k = 1; j; j /= 10, ++k)
    {
        // 头，                尾，             当前位置元素
        int hh = n / ten[k], tt = n % ten[k - 1], cur = j % 10;
        if(hh)
        {
            sum += hh * ten[k - 1];
            if(x == 0) sum -= ten[k - 1];
        }
        else{
            if(x == 0) continue;
        }
        if(cur > x)
            sum += ten[k - 1];
        else if(cur == x) 
            sum += tt + 1;
    }
    printf("\n");
    return sum;
}

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    while(a != 0 || b != 0)
    {
        for(int i = 0; i < 10; ++i)
        {
            if(a > b) swap(a, b);
            printf("%d ", i, count(b, i) - count(a - 1, i));
        }
        puts("");
        scanf("%d %d", &a, &b);
    }
    return 0;
}

/*
93333882 88703970
0 0
*/

/*********************** 状态压缩 ***********************/
const int N = 12, M = 1 << N;
long long f[N][M];
bool st[M];
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    while(n || m)
    {
        memset(f, 0, sizeof f);
        f[0][0] = 1;

        // 预处理出没有连续奇数个0的状态。总状态个数跟行有关，2^n个状态 【注: 只要有连续奇数个0就一定不行】
        int t = 1 << n;
        for(int i = 0 ; i < t; ++i) //枚举所有状态
        {
            int cnt = 0; //记录是否有连续奇数个0
            st[i] = true;
            for(int j = 0; j < n; ++j)
            {
                if(i >> j & 1)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                }
                else
                    ++cnt;
            }
            if(cnt & 1) st[i] = false;
        }

        for(int i = 1; i <= m; ++i)
            for(int j = 0; j < t; ++j)
                for(int k = 0; k < t; ++k)
                    if((j & k) == 0 && st[j | k]) // 上一列的状态必须兼容当前状态，且不存在连续奇数个0
                        f[i][j] += f[i - 1][k];
        
        printf("%lld\n", f[m][0]);
        scanf("%d %d", &n, &m);
    }
    return 0;
}

/* 
// 状态压缩的优化
const int N = 12, M = 1 << N;
long long f[N][M];
bool st[M];
vector<int> state[M];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    while(n || m)
    {
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        int t = 1 << n;
        for(int i = 0 ; i < t; ++i)
        {
            int cnt = 0;
            st[i] = true;
            for(int j = 0; j < n; ++j)
            {
                if((i >> j) & 1)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                }
                else
                    ++cnt;
            }
            if(cnt & 1)
                st[i] = false;
        }
        
        // 预处理出来当前状态为j时，与之相匹配的上一个状态的
        for(int j = 0; j < t; ++j)
        {
            state[j].clear();
            for(int k = 0; k < t; ++k)
                if((j & k) == 0 && st[j | k])
                    state[j].push_back(k);
        }
        
        for(int i = 1; i <= m; ++i)
            for(int j = 0; j < t; ++j)
                for(auto k : state[j])
                    f[i][j] += f[i - 1][k];

        printf("%lld\n", f[m][0]);
        scanf("%d %d", &n, &m);
    }
    return 0;
}
*/

/******************* 树形dp ***************/
// 没有上司的舞会 https://www.acwing.com/problem/content/287/

const int N = 6010;

int H[N];
int h[N], e[N], ne[N], idx;
int f[N][2]; 
// f[i][0] 表示以i为根节点的子树 且不选i 的集合中快乐值最大的那个
// f[i][1] 表示以i为根节点的子树 且选i 的集合中快乐值最大的那个
int d[N]; // d[i] 表示i的入度
bool st[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int i)
{
    st[i] = true;
    for(int j = h[i]; j != -1; j = ne[j])
    {
        int u = e[j];
        if(!st[u])
        {
            dfs(u);
        }
        f[i][0] += max(f[u][0], f[u][1]);
        f[i][1] += f[u][0];
    }
    //printf("%d: %d, %d\n", i, f[i][0], f[i][1]);
}
int main()
{
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; ++i) 
    {
        scanf("%d", &H[i]);
        f[i][1] = H[i];
    }
    for(int i = 0; i < n - 1; ++i)
    {
        int l, k;
        scanf("%d %d", &l, &k);
        add(k, l);
        d[l]++;
    }
    for(int i = 1; i <= n; ++i)
        if(d[i] == 0)
        {
            dfs(i);
            printf("%d", max(f[i][0], f[i][1]));
            break;
        }
    return 0;
}

/**************** 记忆化搜索 ****************/
// 滑雪 https://www.acwing.com/problem/content/903/
int g[310][310];
int ha[310][310]; // ha[i][j] 表示从(i, j)开始划，能划的最大距离
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

int r, c;

// dfs(x, y)返回的是从(x,y)开始滑雪能划的最大距离
int dfs(int x, int y)
{
    if(ha[x][y])
        return ha[x][y];

    int ret = 1;
    for(int i = 0; i < 4; ++i)
    {
        int a = x + dx[i], b = y + dy[i];
        // 这里由于不存在环，所以不需要bool数组记录是否访问过
        if(a > 0 && a <= r && b > 0 && b <= c && g[a][b] < g[x][y])
        {
            int t = 1 + dfs(a, b);
            ret = max(ret, t);
        }
    }
    return ha[x][y] = ret;
}

int main()
{

    scanf("%d %d", &r, &c);
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j)
            scanf("%d", &g[i][j]);
            
    int ans = 1;
    for(int i = 1; i <= r; ++i)
    {
        for(int j = 1; j <= c; ++j)
        {
            int t  = dfs(i, j);
            ans = max(ans, t);
        }
    }
    printf("%d", ans);
    return 0;
}

// 补：状态压缩 最短Hamilton路径 https://www.acwing.com/problem/content/93/
int n, m;
const int N = 22, M = 1 << 20, INF = ~(1 << 31);
int g[N][N];
int dp[M][N];

int main()
{
    cin >> n;
    m = 1 << n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> g[i][j];
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(i & (1 << j))
            {
                for(int k = 0; k < n; ++k)
                {
                    if((i - (1 << j)) & (1 << k))
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k]);
                }
            }
        }
    }
    cout << dp[m - 1][n - 1];
    return 0;
}

#endif
